package com.celan.year2023.month02.day06;

import java.util.*;

public class Solution {
    public boolean evaluateTree(TreeNode root) {
        if (root.val == 0) return false;
        if (root.val == 1) return true;
        if (root.val == 2) return evaluateTree(root.left) || evaluateTree(root.right);
        if (root.val == 3) return evaluateTree(root.left) && evaluateTree(root.right);
        return false;
    }


    public int trailingZeroes(int n) {
        int res = 0;
        while (n > 0) {
            n /= 5;
            res += n;
        }
        return res;
    }

    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) arr[i] = String.valueOf(nums[i]);
        Arrays.sort(arr, (o1, o2) -> (int) (Long.parseLong(o2 + o1) - Long.parseLong(o1 + o2)));
        StringBuilder res = new StringBuilder();
        for (String s : arr) res.append(s);
        if (res.charAt(0) == 0 && res.length() > 1) res.delete(0, 1);
        return res.toString();
    }

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        if (k == 0) return;
        //反转数组
        reverse(nums, 0, n - 1);
        //左右分别反转
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    //左闭右开
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start++, end--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32 && n != 0; i++) {
            res += (n & 1) << (31 - i);
            n >>>= 1;
        }
        return res;
    }

    public int hammingWeight(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans += ((n >> i) & 1);
        }
        return ans;
    }

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer> resList = new ArrayList<>();
        //<课程号,需要提前学习的课程>
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        //记录学过的课程
        HashSet<Integer> set = new HashSet<>();
        //初始化
        for (int[] pair : prerequisites) {
            if (map.containsKey(pair[0])) {
                map.get(pair[0]).add(pair[1]);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(pair[1]);
                map.put(pair[0], list);
            }
        }

        //开始学习
        for (int i = 0; i < numCourses; i++) {
            boolean learn = learn(resList, map, set, i, new HashSet<>());
            if (!learn) return new int[0];
        }

        int[] res = new int[resList.size()];
        for (int i = 0; i < resList.size(); i++) {
            res[i] = resList.get(i);
        }
        return res;
    }

    private boolean learn(List<Integer> resList, HashMap<Integer, List<Integer>> map, HashSet<Integer> set, int idx, HashSet<Integer> need) {
        //这个学过了
        if (set.contains(idx)) return true;
        //无前置条件直接学
        if (!map.containsKey(idx)) {
            resList.add(idx);
            set.add(idx);
            return true;
        }
        //有前置条件
        if (map.containsKey(idx)) {
            //需要学的加入need
            need.add(idx);
            List<Integer> list = map.get(idx);
            for (int i : list) {
                //前置条件出现在need中，说明构成循环
                if (need.contains(i)) return false;
                //前置条件没学过就去学
                if (!set.contains(i)) {
                    //如果学不了 返回false
                    if(!learn(resList, map, set, i, need))return false;
                }
            }
            //学完前置条件学自己
            resList.add(idx);
            set.add(idx);
            need.remove(idx);
        }
        return true;
    }
}
